# test_generator.py
import random


def generate_connected_graph(n, m):
    """生成一个连通的无向图"""
    edges = set()

    # 首先创建一棵生成树确保连通性
    for i in range(2, n + 1):
        j = random.randint(1, i - 1)
        w = random.randint(1, 100)
        edges.add((min(i, j), max(i, j), w))

    # 添加随机边直到达到要求的边数
    while len(edges) < m:
        u = random.randint(1, n)
        v = random.randint(1, n)
        if u != v:
            w = random.randint(1, 100)
            edges.add((min(u, v), max(u, v), w))

    return list(edges)


def generate_test_cases():
    """生成不同规模的测试用例(节点数控制在20以内)"""
    test_cases = []

    # 小规模稀疏图 (5节点，5-8边)
    test_cases.append((5, random.randint(5, 8)))

    # 小规模中等图 (8节点，10-15边)
    test_cases.append((8, random.randint(10, 15)))

    # 中等规模图 (12节点，15-25边)
    test_cases.append((12, random.randint(15, 25)))

    # 中等规模稠密图 (15节点，30-40边)
    test_cases.append((15, random.randint(30, 40)))

    # 较大规模稀疏图 (18节点，20-30边)
    test_cases.append((18, random.randint(20, 30)))

    # 较大规模稠密图 (20节点，40-50边)
    test_cases.append((20, random.randint(40, 50)))

    return test_cases


def save_test_cases_to_file(filename="测试数据.txt"):
    """将测试用例保存到文件"""
    test_cases = generate_test_cases()
    with open(filename, "w") as f:
        f.write(f"{len("测试数据")}\n")  # 写入测试用例数量
        for n, m in test_cases:
            edges = generate_connected_graph(n, m)
            f.write(f"{n} {m}\n")  # 写入节点数和边数
            for u, v, w in edges:
                f.write(f"{u} {v} {w}\n")  # 写入所有边
            f.write("\n")  # 测试用例间用空行分隔
    print(f"测试用例已保存到 {filename}")


if __name__ == "__main__":
    save_test_cases_to_file()